// https://www.lintcode.com/problem/connecting-graph-ii/description

class ConnectingGraph2 {
public:
    /*
    * @param n: An integer
    */
    int* father;
    int* size;
    ConnectingGraph2(int n) {
       father = new int[n + 1]; //注意！！！
       size = new int[n + 1]; //如果是求集合中最大，就改成存max
    //   father = new int[n]; 
    //   size = new int[n];
    //   for (int i = 0; i < n; ++i)
        for (int i = 1; i < n + 1; ++i)
       {
           father[i] = i;
           size[i] = 1;
       }
    }

    /*
     * @param a: An integer
     * @param b: An integer
     * @return: nothing
     */
    void connect(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa != fb)
        {
            father[fa] = fb;
            size[fb] += size[fa]; 
        }
    }
    
    int find(int a)
    {
        int tmp = a;
        while (father[a] != a)
        {
            a = father[a];
        }
        while (tmp != a)
        {
            int ttmp = father[tmp];
            father[tmp] = a;
            tmp = ttmp;
        }
        return a;
    }

    /*
     * @param a: An integer
     * @return: An integer
     */
    int query(int a) {
        // return size[a];
        // return size[father[a]];
        return size[find(a)]; //注意find才是找最根本的根
    }
};